%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Classical Cryptography}
\label{ClassicalCryptography}

\section{Substitution Ciphers}

Classically, cryptosystems were character-based algorithms.
Cryptosystems would substitute characters, permute (or transpose)
characters, or do a combination of those operations.

\begin{center}{\large\bf Notation}\end{center}

Throughout the course we will denote the {\em plaintext alphabet}
by $\cA$ and the {\em ciphertext alphabet} by $\cA'$.  We write $E_K$
for the enciphering map and $D_{K'}$ for the deciphering map, where
$K$ and $K'$ are enciphering and deciphering {keys}.

\begin{center}{\large\bf Substitution Ciphers}\end{center}

We identify four different types of substitution ciphers.
\vspace{3mm}

%\noindent{\bf A. Simple substitution ciphers.}
\subsection*{Simple substitution ciphers}

In this cryptosystem, the algorithm is a character-by-character
substitution, with the key being the list of substitutions under the
ordering of the alphabet.  In other words, a simple substitution
cipher is defined by a map $\cA \rightarrow \cA'$.

Suppose that we first encode a message by purging all nonalphabetic
characters (e.g. numbers, spaces, and punctuation) and changing all
characters to uppercase.  Then the key size, which bounds the security
of the system, is 26 alphabetic characters.  Therefore the total
number of keys is 26!, an enormous number.  Nevertheless, we will see
that simple substitution is very susceptible to cryptanalytic attacks.
\vspace{3mm}

\noindent
{\bf Example.} Consider this paragraph, encoded in this way, to obtain
the plaintext:
\begin{center}
\begin{minipage}[c]{125mm}
\begin{verbatim}
SUPPOSETHATWEFIRSTENCODEAMESSAGEBYPURGINGALLNONALPHABETI
CCHARACTERSEGNUMBERSSPACESANDPUNCTUATIONANDCHANGINGALLCH
ARACTERSTOUPPERCASETHENTHEKEYSIZEWHICHBOUNDSTHESECURITYO
FTHESYSTEMISALPHABETICCHARACTERSTHEREFORETHETOTALNUMBERO
FKEYSISOFENORMOUSSIZENEVERTHELESSWEWILLSEETHATSIMPLESUBS
TITUTIONISVERYSUSCEPTIBLETOCRYPTANALYTICATTACKS
\end{verbatim}
\end{minipage}
\end{center}
then using the enciphering key {\tt ULOIDTGKXYCRHBPMZJQVWNFSAE}, we
encipher the plaintext to obtain ciphertext:
\begin{center}
\begin{minipage}[c]{125mm}
\begin{verbatim}
QWMMPQDVKUVFDTXJQVDBOPIDUHDQQUGDLAMWJGXBGURRBPBURMKULDVX
OOKUJUOVDJQDGBWHLDJQQMUODQUBIMWBOVWUVXPBUBIOKUBGXBGURROK
UJUOVDJQVPWMMDJOUQDVKDBVKDCDAQXEDFKXOKLPWBIQVKDQDOWJXVAP
TVKDQAQVDHXQURMKULDVXOOKUJUOVDJQVKDJDTPJDVKDVPVURBWHLDJP
TCDAQXQPTDBPJHPWQQXEDBDNDJVKDRDQQFDFXRRQDDVKUVQXHMRDQWLQ
VXVWVXPBXQNDJAQWQODMVXLRDVPOJAMVUBURAVXOUVVUOCQ
\end{verbatim}
\end{minipage}
\end{center}
Simple substitution ciphers can be easily broken because the
cipher does not change the frequencies of the symbols of the
plaintext.
\vspace{2mm}

\noindent
{\bf Affine ciphers.} A special case of simple substitution
ciphers are the {\em affine ciphers}.  If we numerically encode
the alphabet $\{{\tt A},{\tt B}\dots,{\tt Z}\}$ as the elements
$\{0,1,\dots,25\}$ of $\Z/26\Z$ then we can operate on the letters
by transformations of the form $x \mapsto ax + b$, for any $a$
for which $\GCD(a,26) = 1$.  {\em What happens if $a$ is not
coprime to 26?}

An affine cipher for which $a = 1$ is called a {\em translation cipher}.
Enciphering in a translation cipher is achieved by the performing $b$
cyclic shift operations ($\tA \mapsto \tB$, $\tB \mapsto \tC$, etc.) on
the underlying alphabet.  Classically a translation cipher is known
as {\bf Caesar's cipher}, after Julius Caesar, who used this method to
communicate with his generals.  For example, using $b = 3$ we obtain
the cipher $\tA \mapsto \tD,\ \tB \mapsto \tE, \dots, \tZ \mapsto \tC$.

%\noindent{\bf B. Homophonic substitution ciphers.}
\subsection*{Homophonic substitution ciphers}

In this cryptosystem the deciphering is a function from a larger alphabet
$\cA'$ to the alphabet $\cA$, but an enciphering of the plaintext can take
a character to any one of the elements in the preimage.

One way to realize a homophonic cipher is to begin with $m$ different
substitution keys, and with each substitution, make a random choice of
which key to use.  For instance, suppose we take $\cA$ to be own standard
26 character alphabet, and let the cipher alphabet $\cA'$ be the set of
character pairs.  Suppose now that we the pair of substitution keys in
the ciphertext alphabet:
\begin{center}
{\tt LV\,MJ\,CW\,XP\,QO\,IG\,EZ\,NB\,YH\,UA\,DS\,RK\,TF\,%
     MJ\,XO\,SL\,PE\,NU\,FV\,TC\,QD\,RK\,YH\,GW\,AB\,ZI} \\
{\tt UD\,PY\,KG\,JN\,SH\,MC\,FT\,LX\,BQ\,EI\,VR\,ZA\,OW\,%
     XP\,HO\,DJ\,CY\,RN\,ZV\,WT\,LA\,SF\,BM\,GU\,QK\,IE}
\end{center}
as our homophonic key.

In order to encipher the message:
\begin{center}
``Always look on the bright side of life.''
\end{center}
we strip it down to our plaintext alphabet to get the plaintext string:
\begin{center}
\begin{minipage}[c]{85mm}
\begin{verbatim}
ALWAYSLOOKONTHEBRIGHTSIDEOFLIFE
\end{verbatim}
\end{minipage}
\end{center}
Then each of the following strings are valid ciphertext:
\begin{center}
\begin{minipage}[c]{150mm}
\begin{verbatim}
LVRKYHLVABZVRKHOHOVRHOXPWTLXQOMJNUYHFTNBTCFVYHJNQOHOMCZABQMCSH
UDZAYHUDQKZVZAHOXODSXOMJTCLXSHMJRNBQFTNBWTZVBQXPQOHOIGZABQMCSH
LVRKYHUDQKZVRKXOXODSHOXPTCLXQOPYRNBQEZNBTCFVBQXPSHHOIGZAYHMCSH
LVZABMUDABFVRKHOHODSHOXPWTLXQOPYRNBQEZNBTCZVBQXPQOXOIGZABQMCQO
\end{verbatim}
\end{minipage}
\end{center}
Moreover, each uniquely deciphers back to the original plaintext.
\vspace{3mm}

%\noindent{\bf C. Polyalphabetic substitution ciphers.}
\subsection*{Polyalphabetic substitution ciphers}

A polyalphabetic substitution cipher, like the homophonic cipher, uses
multiple keys, but the choice of key is not selected randomly, rather
it is determined based on the position within the plaintext.  Most
polyalphabetic ciphers are {\em periodic substitution ciphers}, which
substitutes the $(mj + i)$-th plaintext character using the $i$-th
key, where $1 \le i \le m$.  The number $m$ is called the {\em period}.
\vspace{2mm}

\noindent
{\bf Vigen\`ere cipher.}  The Vigen\`ere cipher is a polyalphabetic
translation cipher, that is, each of the $m$ keys specifies an affine
translation.

Suppose that we take our standard alphabet $\{\tA,\tB,\dots,\tZ\}$ with
the bijection with $\Z/26\Z = \{0,1,\dots,25\}$.  Then beginning with
the message:
\begin{center}
\begin{minipage}[c]{8cm}
\begin{verbatim}
Human salvation lies in the hands
 of the creatively maladjusted.
\end{verbatim}
\end{minipage}
\end{center}
This gives the encoded plaintext:
\begin{center}
\begin{minipage}[c]{12.5cm}
\begin{verbatim}
HUMANSALVATIONLIESINTHEHANDSOFTHECREATIVELYMALADJUSTED
\end{verbatim}
\end{minipage}
\end{center}
The with the enciphering key {\tt UVLOID}, the Vigen\`ere enciphering
is given by performing the column additions:
\begin{center}
\begin{minipage}[c]{14cm}
\begin{verbatim}
HUMANS ALVATI ONLIES INTHEH ANDSOF THECRE ATIVEL YMALAD JUSTED
UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID
--------------------------------------------------------------
BPXOVV UGGOBL IIWWMV CIEVMK UIOGWI NCPQZH UOTJMO SHLZIG DPDHMG
\end{verbatim}
\end{minipage}
\end{center}
Recall that the addition is to be carried out in $\Z/26\Z$, with the
bijection defined by the following table:
$$
\begin{array}{*{26}{c@{\ }}}
\tA & \tB & \tC & \tD & \tE & \tF & \tG & \tH & \tI & \tJ & \tK & \tL & \tM &
\tN & \tO & \tP & \tQ & \tR & \tS & \tT & \tU & \tV & \tW & \tX & \tY & \tZ\\
  0 &   1 &   2 &   3 &   4 &   5 &   6 &   7 &   8 &   9 &  10 &  11 &  12 &
 13 &  14 &  15 &  16 &  17 &  18 &  19 &  20 &  21 &  22 &  23 &  24 &  25
\end{array}
$$
\vspace{2mm}

%\noindent{\bf D. Polygram substitution ciphers.}
\subsection*{Polygram substitution ciphers}

A polygram substitution cipher is a cryptosystem in which blocks of
characters are substituted in groups.  For instance (for a particular
key) {\tt AA} could map to {\tt NO}, {\tt AB} to {\tt IR}, {\tt JU} to
{\tt AQ}, etc.
These cryptosystems make cryptanalysis harder by destroying the single
character frequencies, preserved under simple substitution ciphers.
\vspace{2mm}

\noindent
{\bf General affine ciphers.}
An affine cipher can be generalised to polygram ciphers.  Rather than
a map $m \mapsto c = ma + b$, we can apply a linear transformation of
vectors
$$
u = (m_1,\dots,m_n) \mapsto (c_1,\dots,c_n) = uA + v,
$$
for some invertible matrix $A = (a_{ij})$ and vector
$v = (b_1,\dots,b_n)$.  As before we numerically encode an alphabet
$\{{\tt A},{\tt B}\dots,{\tt Z}\}$ as the elements $\{0,1,\dots,25\}$
of $\Z/26\Z$.  Then each $n$-tuple of characters $m_1m_2\dots m_n$ is
identified with the vector $u = (m_1,m_2,\dots,m_n)$.
Note that matrix multiplication is defined as usual, so that
$$
c_j = (\sum_{i=1}^n m_ia_{ij}) + b_j,
$$
with the result interpreted modulo $26$ as an element of $\Z/26\Z$.

As a special case, consider 2-character polygrams, so that
$$
\tA\tA = (0,0), \dots, \tZ\tY = (25,24), \tZ\tZ = (25,25).
$$
The matrix $A$ given by
$$
\left(\begin{array}{cc} 1 & 8\\21 & 3\end{array}\right)
$$
and vector $v = (13,14)$ defines a map
$$
\begin{array}{c@{\ }l@{\ }c@{\ }l@{\ }c}
\tA\tA & = (\ 0,\ 0) & \mapsto & ( 13, 14) = & \tN\tO \\
%\vdots &             &         &             & \vdots \\
%\tC\tM & = (\ 2, 12) & \mapsto & (\ 7, 14) = & \tH\tO \\
\vdots &             &         &             & \vdots \\
\tZ\tY & = ( 25, 24) & \mapsto & ( 18, 23) = & \tW\tA \\
\tZ\tZ & = ( 25, 25) & \mapsto & ( 18, 23) = & \tR\tD \\
\end{array}
$$
which is a simple substitution on the 2-character polygrams.  Note that
the number of affine ciphers is much less than all possible substitutions,
but grows exponentially in the number $n$ of characters.

%\begin{center}{\Large\bf MATH3024: Lecture 03}\end{center}

\section{Transposition Ciphers}

Recall that a substitution cipher permutes the characters of the
plaintext alphabet, or may, more generally, map the plaintext
characters into a different ciphertext alphabet.
In a {\em transposition cipher}, the symbols of the plaintext
remain the same unchanged, but their order is permuted by a
permutation of the index positions.  Unlike substitution
ciphers, transposition ciphers are {\em block ciphers}.

The relation between substitution ciphers and transposition ciphers
is illustrated in Table~\ref{table-substrans}.
The characters and their positions of the plaintext string {\tt ACATINTHEHAT}
appear in a graph with a character axis $c$ and a position index $i$ for the
$12$ character block $1 \le i \le n$.
We represented as a graph a substitution cipher (with equal plaintext and
ciphertext alphabets) is realised as a permutation of the rows of the array,
while a transposition cipher is realised by permuting the columns in fixed
size blocks, in this case $12$.

\begin{table}[ht]
\renewcommand{\tmp}{\arraystretch}
\renewcommand{\arraystretch}{0.6}
\begin{center}
\begin{tabular}[t]{r@{\ \ }l@{\ }*{12}c@{\ }l@{}}
\cline{2-14}
\tZ & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tY & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tX & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tW & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tV & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tU & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tT & \vline &   &   &   &\tT&   &   &\tT&   &   &   &   &\tT& \vline\\
\tS & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tR & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tQ & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tP & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tO & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tN & \vline &   &   &   &   &   &\tN&   &   &   &   &   &   & \vline\\
\tM & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tL & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tK & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tJ & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tI & \vline &   &   &   &   &\tI&   &   &   &   &   &   &   & \vline\\
\tH & \vline &   &   &   &   &   &   &   &\tH&   &\tH&   &   & \vline\\
\tG & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tF & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tE & \vline &   &   &   &   &   &   &   &   &\tE&   &   &   & \vline\\
\tD & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tC & \vline &   &\tC&   &   &   &   &   &   &   &   &   &   & \vline\\
\tB & \vline &   &   &   &   &   &   &   &   &   &   &   &   & \vline\\
\tA & \vline &\tA&   &\tA&   &   &   &   &   &   &   &\tA&   & \vline\\
\cline{2-14}\\
&& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{\tmp}
\caption{Transposition and substitution axes for {\tt ACATINTHEHAT}}
\label{table-substrans}
\end{table}

\subsection*{Permutation groups}

The {\it symmetric group} $S_n$ is the set of all bijective maps
from the set $\{1,\dots,n\}$ to itself, and we call an elements
$\pi$ of $S_n$ a permutation.
We denote the $n$-th composition of $\pi$ with itself by $\pi^n$.
As a function write $\pi$ on the left, so that the image of $j$
is $\pi(j)$.
An element of $S_n$ is called a {\it transposition} if and only
if it exchanges exactly two elements, leaving all others fixed.

%\begin{center}{\large\bf Notation for Permutations}\end{center}
\subsection*{List notation for permutations}

The map $\pi(j) = i_j$ can be denoted by $[i_1,\dots,i_n]$. This is
the way, in effect, that we have described a key for a substitution
cipher --- we list the sequence of characters in the image of \tA,
\tB, \tC, etc.  Although these permutations act on the set of the
characters $\tA,\dots,\tZ$ rather than the integers $1,\dots,n$,
the principle is identical.

%\begin{center}{\large\bf Orbit Structure and Cycle Notation}\end{center}
\subsection*{Cycle notation and orbit structure}

Given a permutation $\pi$ in $S_n$ there exists a unique {\it orbit
decomposition}:
$$
\{1,\dots,n\} = \bigcup_{k=1}^t \{\pi^j(i_k)\,:\,j\in\Z\},
$$
where union can be taken over disjoint sets, i.e.~$i_k$ is not equal
to $\pi^j(i_\ell)$ for any $j$ unless $k = \ell$.
The sets $\{\pi^j(i_k)\,:\,j\in\Z\}$ are called the {\em orbits} of
$\pi$, and the cycle lengths of $\pi$ are the sizes $d_1,\dots,d_t$ of
the orbits.

Associated to any orbit decomposition we can express an element
$\pi$ as
$$
\pi = \left(i_1,\pi(i_1),\dots,\pi^{d_1-1}(i_1)\right) \cdots
      \left(i_t,\pi(i_t),\dots,\pi^{d_t-1}(i_t)\right)
$$
Note that if $d_k = 1$, then we omit this term, and the identity
permutation can be written just as $1$. This notation gives more
information about the permutation $\pi$ and is more compact for
simple permutations such as transpositions.

%\begin{center}{\large\bf Simple Columnar Transposition}\end{center}
\subsection*{Simple columnar transposition}

A classical example of a transposition cipher is an $(r,s)$-simple
columnar transposition.  In this cryptosystem the plaintext is written
in blocks as $r$~rows of fixed length~$s$.  The ciphertext is read off
as the columns of this array.  Suppose we begin with the plaintext:
\begin{center}
\begin{minipage}[c]{8cm}
\begin{verbatim}
I was riding on the Mayflower
When I thought I spied some land
I yelled for Captain Arab
I have yuh understand
Who came running to the deck
Said, "Boys, forget the whale
Look on over yonder
Cut the engines
Change the sail
Haul on the bowline"
We sang that melody
Like all tough sailors do
When they are far away at sea
\end{verbatim}
\end{minipage}
\end{center}
Stripped to our plaintext alphabet and written in lines of 36 characters
each, we have the plaintext:
\begin{center}
\begin{minipage}[c]{9cm}
\begin{verbatim}
IWASRIDINGONTHEMAYFLOWERWHENITHOUGHT
ISPIEDSOMELANDIYELLEDFORCAPTAINARABI
HAVEYUHUNDERSTANDWHOCAMERUNNINGTOTHE
DECKSAIDBOYSFORGETTHEWHALELOOKONOVER
YONDERCUTTHEENGINESCHANGETHESAILHAUL
ONTHEBOWLINEWESANGTHATMELODYLIKEALLT
OUGHSAILORSDOWHENTHEYAREFARAWAYATSEA
\end{verbatim}
\end{minipage}
\end{center}
Reading off the columns, we obtain the following ciphertext under
the columnar transposition cipher:
\begin{center}
\begin{minipage}[c]{10cm}
\begin{verbatim}
IIHDYOOWSAEONUAPVCNTGSIEKDHHREYSEESIDUARBA
DSHICOIIOUDUWLNMNBTLOGEDOTIROLEYHNSNARSEED
TNSFEWOHDTONEWEIARGSHMYNGIAEAEDENNNYLWTEGT
FLHTSTHLEOHCHEODCEHAYWFAWATAEOMHNMRRREAGEE
WCRLELFHAUETOAEPNLHDRNTNOEYAIAIOSLWTINKAIA
HNGOIKYOATNLEAUROOHATGATVALSHBHEULETIERLTA
\end{verbatim}
\end{minipage}
\end{center}
Simple columnar transpositions impose unnecessarily restrictive conditions
on the form of the transposition, but were widely used as a component of
ciphers used until the 1950's.  More general columnar transpositions allow
for permutations of the columns before reading them off.

\subsection*{General transposition ciphers}

\ignore{
I was riding on the Mayflower
When I thought I spied some land
I yelled for Captain Arab
I have yuh understand
Who came running to the deck
Said, ``Boys, forget the whale
Look on over yonder
Cut the engines
Change the sail
Haul on the bowline''
We sang that melody
Like all tough sailors do
When they are far away at sea
}
A general transposition cipher of block length $m$ allows $m!$ different
permutations.  For $m = 7$, this is a mere $5040$ permutations, but for
block length 36, this gives
$$
371993326789901217467999448150835200000000
$$
possibilities.  One such permutation, given in cycle notation, is:
$$
\begin{array}{c}
\multicolumn{1}{l}{(1,12,5,36,30,31,4,28,33,22,26,17,10,16,14,23,18,35,32)\qquad}\\
\multicolumn{1}{r}{\qquad(2,9,3,25,15,7,21,6,29,34,11,27,19,24)(8,13,20).}
\end{array}
$$
Applied to the above ciphertext this gives a the ciphertext
\begin{center}
\begin{minipage}[c]{8cm}
\begin{verbatim}
NNWNTIOTAMERLEDHGHRIIHYWEAFUGHSIWOOT
AMCTIADNPYPEEOSDEBRODALSIELRANIIFLAI
RNRNEICSVNNYOMHTDHEUUUWAADHOTGEHAETN
SBLOROEFCGLSHHIOOEADAETERETOVOKDWYNK
ETEELSHENIHECNCNTUGURTEOGNSHAIDYAHLA
ELLYTLAWTADEHMOEILEWBOGNSNTALKHOTNEI
DOFAAWYOGERSERIWREELAATUHNHTSYHOASAA
\end{verbatim}
\end{minipage}
\end{center}
Despite the large number of possible permutations, the unmasked structure of the
plaintext permits an adversary to decipher transposition ciphertext.

\section*{Exercises}

\input{exercises/ClassicalCryptography}
